package com.rizhov.tasks;

import java.util.ArrayList;

import com.rizhov.graph.Graph;

public class FirstTask implements Task {

    /** graph connected with that task */
    private Graph graph;

    /** result string contains edges to be built */
    protected String resultString;

    private FirstTask() {
	calculateTask();
    }

    public FirstTask(Graph graph) {
	this.graph = graph;
	resultString = "";
    }

    @Override
    public Object clone() {
	FirstTask copy = new FirstTask();
	copy.graph = this.graph;
	copy.resultString = this.resultString;
	return copy;
    }	

    /*
     * (non-Javadoc)
     * 
     * @see com.rizhov.graph.Task#setGraph(com.rizhov.graph.Graph)
     */
    @Override
    public void setGraph(Graph graph) {
	this.graph = graph;
	calculateTask();
    }

    /*
     * (non-Javadoc)
     * 
     * @see com.rizhov.graph.Task#restart()
     */
    @Override
    public void restart() {
	calculateTask();
    }

    /*
     * (non-Javadoc)
     * 
     * @see com.rizhov.graph.Task#getResult()
     */
    @Override
    public String getResult() {
	return resultString;
    }

    private static class ColoredVertex {

	/** color of vertex */
	protected VertexColor color;

	/** indexes of connected vertexes */
	protected ArrayList<Integer> adj;

	protected int d; // время обнаружения
	protected int f; // время закраски черным

	public static enum VertexColor {
	    WHITE, GRAY, BLACK;
	}
    }

    public void calculateTask() {
	StringBuffer sb = new StringBuffer();
	// tree number array
	int[] treeNumber = new int[graph.getVertexCount()];
	int countOfTrees = depthFirstSearch(treeNumber);
	if (countOfTrees != 1) {
	    for (int i = 1; i < countOfTrees; i++) {
		int startVertex = -1;
		int endVertex = -1;
		for (int j = 0; j < treeNumber.length; j++) {
		    if (treeNumber[j] == i) {
			startVertex = j;
		    }
		    if (treeNumber[j] == i + 1) {
			endVertex = j;
		    }
		}
		sb.append("(" + startVertex + " ~ " + endVertex + ")");
	    }
	    resultString = sb.toString();
	} else {
	    resultString = "Graph is alredy connected!";
	}
    }

    public int depthFirstSearch(int[] treeNumber) {
	// graph vertexes
	ArrayList<ColoredVertex> coloredVertexArr = new ArrayList<ColoredVertex>();

	// global time, it's needed for algorithm
	Integer time = 0;
	
	int currentTreeNumber = 1;

	for (int i = 0; i < graph.getVertexCount(); i++) {
	    ColoredVertex tempColoredVertex = new ColoredVertex();
	    tempColoredVertex.color = ColoredVertex.VertexColor.WHITE;
	    tempColoredVertex.adj = new ArrayList<Integer>();
	    for (int j = 0; j < graph.getVertexCount(); j++) {
		if (graph.isEdgeExist(i, j)) {
		    tempColoredVertex.adj.add(j);
		}
	    }
	    coloredVertexArr.add(tempColoredVertex);
	}
	for (int i = 0; i < graph.getVertexCount(); i++) {
	    if (coloredVertexArr.get(i).color == ColoredVertex.VertexColor.WHITE) {
		treeNumber[i] = currentTreeNumber;
		dfsVisit(i, time, coloredVertexArr, treeNumber, currentTreeNumber);
		currentTreeNumber++;
	    }
	}
	currentTreeNumber--;
	return currentTreeNumber;
    }

    public void dfsVisit(int index, Integer time, ArrayList<ColoredVertex> coloredVertexArr, int[] treeNumber, int currentTreeNumber) {
	ColoredVertex tempVertex = coloredVertexArr.get(index);
	tempVertex.color = ColoredVertex.VertexColor.GRAY;
	tempVertex.d = time;
	time++;
	for (int edgeIndex : tempVertex.adj) {
	    if (coloredVertexArr.get(edgeIndex).color == ColoredVertex.VertexColor.WHITE) {
		treeNumber[index] = currentTreeNumber;
		dfsVisit(edgeIndex, time, coloredVertexArr, treeNumber, currentTreeNumber);
	    }
	}
	tempVertex.color = ColoredVertex.VertexColor.BLACK;
	tempVertex.f = time;
	time++;
    }

}
